1. Field of the Invention
The present invention relates to a method and a program for determining insides and outsides of two-dimensional or three-dimensional boundary surfaces.
2. Description of the Related Art
In the field of research and technique, a CAD (Computer Aided Design), a CAM (Computer Aided Manufacturing), a CAE (Computer Aided Engineering), a CAT (Computer Aided Testing), and the like are used as simulation means for designing, machining, analyzing, and testing, respectively.
In the case of the above conventional simulation means, a boundary surface of an object is important. For example, generally, the object is expressed by the boundary surface, and the inside of the boundary surface is uniformly treated. In such a case, it is necessary to use inside/outside determination method for determining the inside and the outside of the two-dimensional or three-dimensional boundary surface.
As a conventional inside/outside determination method, there is known (1) a ray crossing method, (2) a region growing (expanding) method that uses boundary tracking, (3) raster tracking in image processing, (4) multi-directional tracking, (5) a Curless method, (6) a Szeliski method and a Puli method that use oct-tree, Japanese Laid-Open Patent Publication Nos. 8-153214 and 9-81783, and so on.
(1) In the region growing method (the ray crossing method), when a boundary surface is input, the inside and the outside of an object is determined based on whether the number of intersecting points of the boundary with a light ray (having a trajectory of a half line) emitted from a certain point is even or odd. That is, when the number of the intersecting points is even, the light ray emitting point (the certain point) is outside the object, and when the number of the intersecting points is odd, the light emitting point is inside the object. This region growing (expanding) method is disclosed in “Computational geometry in C second edition” (J. O'Rourke, p. 246, Cambridge University Press, 1998).
However, the region growing (expanding) method cannot be applied to a case where the light ray accidentally comes in contact with the boundary surface because the number of intersecting points that should be two becomes one due to a repeated root. Further, the region growing method cannot be applied to a case where boundary information has a defect (data lack caused by a numerical value error or expression difference when reading data from different software by using CAD data).
(2) The region growing (expanding) method that uses boundary tracking in image processing when only boundary information is given is disclosed in “Digital Image Processing” (Rosenfeld & Kak, translator: Nagao, Kindaikagakusha, pp. 353-357), for example. However, since the processing is performed over an entire region, the processing takes time. Further, when the surface information has a defect, the outside/inside determination cannot be performed accurately.
(3) The raster tracking in image processing is disclosed in the above “Digital Image Processing” (p. 334), and is a method in which a boundary and a region sandwiched by the boundaries are tracked while scanning a cell along a coordinate axis such as an X axis. However, when a quantized image is formed from the boundary information having a defect, accurate inside/outside determination cannot be performed.
(4) In order to avoid this problem, the multi-directional tracking (disclosed in the above “Digital Image Processing”, p. 332) can be used, but efficiency of this method is low.
(5) In the Curless method in the field of a reverse engineering (that restructures surface information from a group of measured points), external information such as a measured object and plural camera directions to regularly arranged measured points is used, and an implicit function based on a distance is defined in an entire field so that surface information can be restructured. This method is robust, and disclosed in “A volume tric method for building complex models from range images.” (B. Curless and M. Levoy, In Proceedings of SIGGRAPH '96, pages 303-312, Aug. 1996).
However, in the Curless method, it is necessary to perform a calculation in a distance field for all cells, so that there is a demerit in terms of a data amount and a calculation time. Furthermore, an accuracy problem is pointed out. For example, a distance function cannot be accurately calculated in a structure thinner than a cell or at a sharp surface. This causes an error in the inside/outside determination.
(6) The Szeliski method and the Pulli method that use the oct-tree are also a method in which data is classified into the inside, the outside, and the boundary based on the relation between several obtained target range data (distance data) and cells divided from a space by the oct-tree to restructure the boundary. The Szeliski method is disclosed in “Rapid octree construction from image sequences” R. Szeliski., and the Pulli method is disclosed in “Robust meshes from multiple range maps” K. Pulli, T. Duchamp, H. Hoppe, J. McDonald, L. hapiro, W. Stuetzle. Proceedings of International Conference on Recent Advances in 3-D digital Imaging and Modeling, May 1997, pages 205-211. In these methods, a projection operation is performed for each cell, so that a process becomes complicated and takes time, and a calculation in the projection operation is unstable.
In “Method for generating three-dimensional orthogonal lattice data” of Japanese Laid-Open Patent Publication No. 8-153214, after a surface lattice and a vacant voxel are distinguished from each other, a reversing operation is performed to generate the surface lattice. This method can cope with up to two types of media, and it is difficult or impossible that this method is applied to three or more types of media.
In “Finite element model processing system and method for the same” of Japanese Laid-Open Patent Publication No. 9-81783, it is determined whether or not an area of a target division element matches a total area of triangles constituted by a target node and every two of vertexes of this division element. However, there is a problem in that this method cannot be applied to a case where the boundary information has a defect.